package com.chj.zhongji.class06;

import java.util.LinkedList;
import java.util.Queue;

public class Code02_BSTtoDoubleLinkedList {
		//	https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
		//	https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
			public static class Node {
				public int val;
				public Node left;
				public Node right;

				public Node(int data) {
					this.val = data;
				}
			}

			public static Node convert1(Node root) {
				Queue<Node> queue = new LinkedList<Node>();
				inOrderToQueue(root, queue);
				if (queue.isEmpty()) {
					return root;
				}
				root = queue.poll();
				Node pre = root;
				pre.left = null;
				Node cur = null;
				while (!queue.isEmpty()) {
					cur = queue.poll();
					pre.right = cur;
					cur.left = pre;
					pre = cur;
				}
				pre.right = null;
				return root;
			}

			public static void inOrderToQueue(Node head, Queue<Node> queue) {
				if (head == null) {
					return;
				}
				inOrderToQueue(head.left, queue);
				queue.offer(head);
				inOrderToQueue(head.right, queue);
			}

			public static Node convert2(Node root) {
				if (root == null) {
					return null;
				}
				return process(root).start;
			}

			public static class RetrunType {
				public Node start;
				public Node end;

				public RetrunType(Node start, Node end) {
					this.start = start;
					this.end = end;
				}
			}

			// 以x为头的整棵搜索二叉树，请全部以有序双向链表的方式，连好
			// 并且返回，整个有序双向链表的头节点和尾节点
			public static RetrunType process(Node root) {
				if (root == null) {
					return new RetrunType(null, null);
				}
				RetrunType leftHeadEnd = process(root.left);
				RetrunType rightHeadEnd = process(root.right);
				if (leftHeadEnd.end != null) {
					leftHeadEnd.end.right = root;
				}

				root.left = leftHeadEnd.end;
				root.right = rightHeadEnd.start;
				if (rightHeadEnd.start != null) {
					rightHeadEnd.start.left = root;
				}

				if (leftHeadEnd.start != null && rightHeadEnd.end != null) {
					return new RetrunType(leftHeadEnd.start, rightHeadEnd.end);
				}

				if (leftHeadEnd.start == null && rightHeadEnd.end != null) {
					return new RetrunType(root, rightHeadEnd.end);
				}

				if (leftHeadEnd.start != null && rightHeadEnd.end == null) {
					return new RetrunType(leftHeadEnd.start, root);
				}

				return new RetrunType(root, root);
			}

			public static void printBSTInOrder(Node head) {
				System.out.print("BST in-order: ");
				if (head != null) {
					inOrderPrint(head);
				}
				System.out.println();
			}

			public static void inOrderPrint(Node head) {
				if (head == null) {
					return;
				}
				inOrderPrint(head.left);
				System.out.print(head.val + " ");
				inOrderPrint(head.right);
			}

			public static void printDoubleLinkedList(Node head) {
				System.out.print("Double Linked List: ");
				Node end = null;
				while (head != null) {
					System.out.print(head.val + " ");
					end = head;
					head = head.right;
				}
				System.out.print("| ");
				while (end != null) {
					System.out.print(end.val + " ");
					end = end.left;
				}
				System.out.println();
			}

			public static void main(String[] args) {
				Node head = new Node(5);
				head.left = new Node(2);
				head.right = new Node(9);
				head.left.left = new Node(1);
				head.left.right = new Node(3);
				head.left.right.right = new Node(4);
				head.right.left = new Node(7);
				head.right.right = new Node(10);
				head.left.left = new Node(1);
				head.right.left.left = new Node(6);
				head.right.left.right = new Node(8);

				printBSTInOrder(head);
				head = convert1(head);
				printDoubleLinkedList(head);

				head = new Node(5);
				head.left = new Node(2);
				head.right = new Node(9);
				head.left.left = new Node(1);
				head.left.right = new Node(3);
		head.left.right.right = new Node(4);
		head.right.left = new Node(7);
		head.right.right = new Node(10);
		head.left.left = new Node(1);
		head.right.left.left = new Node(6);
		head.right.left.right = new Node(8);

		printBSTInOrder(head);
		head = convert2(head);
		printDoubleLinkedList(head);

	}
}
